package lhc.alg.top100;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

/**
 * description: lfu 平衡二叉树+哈希表
 * author: hongchen.liao
 * date:  2022/7/21
 */
public class _460_LFU {

    class LFUCache {

        //定义一个辅助节点类
        class Node implements Comparable<Node>{
            int cnt, time, key, value;

            Node(int cnt, int time, int key, int value){
                this.cnt = cnt;
                this.time = time;
                this.key = key;
                this.value = value;
            }

            public boolean equals(Object anObject){
                if(this == anObject){
                    return true;
                }
                if(anObject instanceof Node){
                    Node rhs = (Node) anObject;
                    return this.cnt == rhs.cnt && this.time == rhs.time;
                }
                return false;
            }

            public int compareTo(Node rhs){
                return cnt == rhs.cnt ? time - rhs.time : cnt - rhs.cnt;
            }

            public int hashCode(){
                return cnt * 1000000007 + time;
            }

        }

        //缓存容量，时间戳
        int capacity, time;
        Map<Integer, Node> key_table;
        TreeSet<Node> S;

        public LFUCache(int capacity) {
            this.capacity = capacity;
            this.time = 0;
            key_table = new HashMap<>();
            S = new TreeSet<>();
        }

        public int get(int key) {
            if(capacity == 0){
                return -1;
            }
            if(!key_table.containsKey(key)){
                return -1;
            }
            //从哈希表中得到旧的缓存
            Node cache = key_table.get(key);
            //从平衡二叉树删除旧的缓存
            S.remove(cache);
            //将旧缓存更新
            cache.cnt += 1;
            cache.time = ++time;
            //将新缓存重新放入哈希表与平衡二叉树中
            S.add(cache);
            key_table.put(key, cache);
            return cache.value;
        }

        public void put(int key, int value) {
            if(capacity == 0){
                return;
            }
            if(!key_table.containsKey(key)){
                //如果到达缓存容量上限
                if(key_table.size() == capacity){
                    //从哈希表与平衡二叉树中删除最近最少使用的缓存
                    key_table.remove(S.first().key);
                    S.remove(S.first());
                }
                //创建新的缓存
                Node cache = new Node(1, ++time, key, value);
                //将新缓存加入这个哈希表与平衡二叉树
                key_table.put(key, cache);
                S.add(cache);
            }else{
                //下面这里与get()函数类似

                //从哈希表中得到旧的缓存
                Node cache = key_table.get(key);
                //从平衡二叉树删除旧的缓存
                S.remove(cache);
                //将旧缓存更新
                cache.cnt += 1;
                cache.time = ++time;

                cache.value = value;//额外需要赋值value

                //将新缓存重新放入哈希表与平衡二叉树中
                S.add(cache);
                key_table.put(key, cache);

            }

        }
    }


}
